package demo.practice.dp;

public class NumMatrix {


    //P304
    int[][] store;

    public NumMatrix(int[][] matrix) {

        //前缀和，矩阵如果整体多一列，可以做类似的操作
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return;

        store = new int[matrix.length][matrix[0].length + 1];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                store[i][j + 1] = store[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (store == null)
            return 0;

        if(row1<0|| row2 >= store.length || row1>row2)
            return 0;

        if(col1<0|| col2 >= store[0].length-1 || col1>col2)
            return 0;


        int sum=0;
        for( int i=row1;i<=row2;i++){
            sum+=(store[i][col2+1]-store[i][col1]);
        }
        return sum;
    }

}
